【ACM-ICPC 2018 南京赛区网络预赛】Set <并查集+Trie合并>

Problem

【ACM-ICPC 2018 南京赛区网络预赛】Set

Description

Shinku is very interested in the set. One day, she got sets, and the number is in the set. But she doesn’t think it is interesting enough, so she applies magic to these sets. There are three kinds of magic:

: If the and numbers are not in one set, then the Shinku’s magic will merge the set containing the number and the set containing the number.
: Shinku’s magic adds to each number in the set containing the number.
: Shinku can immediately know how many numbers in the set containing the number satisfy .

But unfortunately, for some reason the type magic fails. So Shinku wants you to tell her the answer after every type magic.
Note that there can be multiple numbers with the same value in one set, that is, numbers with the same value will not disappear when merged.

Input

The first line contains two integers , the number of initial sets and the number of the magic.
The second line contains integers. The number is the number in the set initially.
The next lines describe the sequence of magic. The line describes the magic. Each magic is a magic as described above.

Output

For each type magic, output the answer you are asked to calculate.

Sample Input

Sample Output

1
2

2
3

Explanation

After the first operation, the numbers are , sets are
For the second operation, the third number is in , , , so the answer is .
After the third operation, the numbers are , sets are
After the forth operation, the numbers are , sets are
For the fifth operation, ,the third number is in , , ,, so the answer is .

Source

ACM-ICPC 2018 南京赛区网络预赛

标签：并查集 Trie合并

Translation

给定一个长为的序列，起初第个数在第个集合。
有个操作，分为三类：

将第个数和第个数所在集合合并
将第个数所在集合所有数加
问所在集合有多少个数模余

对于每个询问，输出答案。

Solution

探索题目条件的特殊性，发现所有询问均是对取模。
我们将每个数转为二进制后倒置，则询问变为含有转为二进制倒置作为前缀的二进制串的个数，可以用维护。那么操作相当于合并两个，可以用类似线段树合并的做法完成，需要用并查集维护连通性。
对于操作，由于每个数都倒置了，可以模拟从最后一位向前进位。于是给结点打上标记，每次下传时将标记除传到下一层，特别地，如果当前层标记是奇数，则需要交换两个子树，因为进位会使变为，变为。
总时间复杂度。
貌似对操作可以暴力向下递归交换子树。

Code

#include <bits/stdc++.h>
#define MAX_N 600000
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, sz, rt[MAX_N+5], fa[MAX_N+5];
struct node {int s[2], c, tag;} tr[MAX_N*32];
int getf(int x) {return fa[x] == x ? x : fa[x] = getf(fa[x]);}
void downtag(int v) {
    if (!tr[v].tag) return;
    if (tr[v].tag&1)
        tr[tr[v].s[1]].tag++, 
        swap(tr[v].s[0], tr[v].s[1]);
    if (tr[v].tag > 1)
        tr[tr[v].s[0]].tag += (tr[v].tag>>1), 
        tr[tr[v].s[1]].tag += (tr[v].tag>>1);
    tr[v].tag = 0;
}
void insert(int &v, int dep, int x) {
    if (!v) v = ++sz;
    if (!dep) {tr[v].c++; return;}
    insert(tr[v].s[x&1], dep-1, x>>1);
    tr[v].c = tr[tr[v].s[0]].c+tr[tr[v].s[1]].c;
}
int merge(int u, int v) {
    if (!u) return v; if (!v) return u;
    downtag(u), downtag(v);
    tr[u].s[0] = merge(tr[u].s[0], tr[v].s[0]);
    tr[u].s[1] = merge(tr[u].s[1], tr[v].s[1]);
    tr[u].c += tr[v].c; return u;
}
int main() {
    read(n), read(m);
    for (int i = 1, x; i <= n; i++)
        fa[i] = i, read(x), insert(rt[i], 30, x);
    while (m--) {
        int opt, p, u, v, k, x; read(opt);
        if (opt == 1) {
            read(u), read(v), u = getf(u), v = getf(v);
            if (u^v) fa[v] = u, rt[u] = merge(rt[u], rt[v]);
        }
        if (opt == 2) read(p), tr[rt[getf(p)]].tag++;
        if (opt == 3) {
            read(p), read(k), read(x), p = rt[getf(p)];
            for (; k; k--, p = tr[p].s[x&1], x >>= 1) downtag(p);
            printf("%d\n", p ? tr[p].c : 0);
        }
    }
    return 0;
}